package done.easy_201_300;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 204. Count Primes
 * <p>
 * 统计所有小于非负整数 n 的质数的数量。
 * <p>
 * 示例:
 * 输入: 10
 * 输出: 4
 * 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
 * <p>
 * 这道题给定一个非负数n，让我们求小于n的质数的个数，题目中给了充足的提示
 * ，解题方法就在第二个提示埃拉托斯特尼筛法Sieve of Eratosthenes中，
 * 这个算法的过程如下图所示，我们从2开始遍历到根号n，先找到第一个质数2，
 * 然后将其所有的倍数全部标记出来，然后到下一个质数3，标记其所有倍数，
 * 一次类推，直到根号n，此时数组中未被标记的数字就是质数。我们需要一个
 * n-1长度的bool型数组来记录每个数字是否被标记，长度为n-1的原因是题目说是
 * 小于n的质数个数，并不包括n。 ：
 * 2019-03-24 7:41 PM
 **/
@Slf4j
public class CountPrimes {

    @SuppressWarnings("all")
    public int countPrimes(int n) {
        // 190324 first
        return -1;
    }

    @Test
    public void test() {
        log.info("result:{}", countPrimes(10));
    }
}
























/*
public int countPrimes(int n) {
    boolean[] isPrime = new boolean[n + 1];

    int count = 0;

    // 质数都是2开始的
    for (int i = 2;  i < n; i++) {

        // isPrime是标记位，初始位 false
        if (isPrime[i] == false) {

            count++;

            for (int j = i + i; j < n; j += i) {
                isPrime[j] = true;
            }

        }
    }

    return count;
}
*/
